1.40

题目

Recall that string $x$ is a prefix of string $y$ if a string $z$ exists such where $x z = y$ ,
and that $x$ is a proper prefix of $y$ if in addition $x \neq y$ . In each of the following parts, we define an operation on a language $A$ . Show that the class of regular languages is closed under that operation.

NOPREFIX (A) = {w \in A ∣ no proper prefix of w is a member of A} .

NOEXTEND (A) = {w \in A ∣ w is not the proper prefix of any string in A} .

思路

点击展开

a.
在 A 的 DFA 中添加限制：只允许到达一次接受状态，不允许多次到达。

b.
我们希望接受那些不可能通过添加后缀而到达新接受状态的字符串，一个重要的观察是，这只和字符串到达的最后一个接受状态有关。所以，必须也只需让某些接收状态失去资格，变为拒绝状态

解答

点击展开

a.
在 A 的 DFA 中删除接受状态的出边，形成新的 NFA，对应 NOPREFIX(A)

b.
在 A 的 DFA 中同时将满足如下条件的接受状态改为拒绝状态：存在从该状态到接受状态的路径，形成新的 DFA，对应 NOEXTEND(A)